import java.util.HashMap;

class Solution560 {
    public static void main(String[] args) {
        int[] nums = {1,1,1};
        int k = 2;
        Solution560 solution = new Solution560();
        System.out.println(solution.subarraySum(nums, k));
    }

    /*
    *前缀和
    * a[i:j+1] = pre[j] - pre[i-1]
    */
    public int subarraySum(int[] nums, int k) {
        int value = 0 , count = 0, u;
        HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();
        dict.put(0,1); //添加0,1, 否则第一个数字永远算不上
        for (int i : nums) {
            value += i;
            u = value - k;
            count += dict.getOrDefault(u, 0);
            dict.put(value, dict.getOrDefault(value, 0)+1);
        }
        return count;
    }
}